XXI Open Cup. GP of Korea

imily's notebook

2021-04-27

$A$

POI-LOG？这里的 $s$ 不相同。放到方阵上看你就输了！

把 $a$ 降序排列。答案为 $1$ 的充要条件：$\forall k, \sum\limits_{i = 1}^k a_i \leq \sum\limits_{j = 1}^m \min(b_j, k)$

证明考虑网络流模型，连边 $(S, i, a_i)$, $(j, T, b_j)$, 若 $maxflow = \sum a_i$ 则答案为 $1$。

考虑割的话一定是割一段 $a$ 的后缀和一段 $b$ 的前缀，即 $\sum\limits_{i = k + 1}^{n} a_i + \sum\limits_{i = 1}^{|B_{cut}|} b_i + \sum\limits_{i = |B_{cut}| + 1}^m k \geq mincut = \sum\limits_{i = 1}^n a_i$，整理得到上柿。

来个什么 DS 维护一下 min。由于每次只改变 $1$，操作都很容易维护。$a$ 相等，减的话减最后面的，加的话加最前面的，位置二分得到。注意 long long（

我在写什么我个憨憨。

$Code$

$B$

$(1, 1)$ 能到达 $(n, m)$ 的充要条件是：

不存在一行或一列被阻断
同时起始点不被阻断。

证明也很清真：因为不存在一行或一列被阻断，任选一个好点 $(r, c)$；$(r, c)$ 必然能往上或往左走，不然就是「起点被阻断」了，矛盾。

枚举 $S$ 所在行，$T$ 所在的位置，对于条件 1，显然具有单调性；对于条件 2，维护单调栈，ban 掉一些起点，终点类似。具体来说，枚举 $x$，ban 掉 $x$ 坐标小于 $x$ 的离它最近的起点，找这个可以考虑找到最左边的列 $j$ 满足 $a_x + b_j \geq 0$，$j$ 左边找到 $b_j$ 最小的 $y$ 处，再找 $x$ 坐标最大的小于 $x$ 的 $i$ 满足 $a_i + b_y \leq 0$，$[i + 1, x]$ 的都不能成为起点了。

代码咕了

$C$

给一个边双定向使得强连通并且路价最小。

构造强连通图的方法：耳分解，即每次选一条起终点在已构造 SCC 里，除起终点外的点都不在 SCC 里的路径，拼到 SCC 里。

dp, $dp[s, u, v]$ 表示当前已加入集合 $s$ 的点，还需填充 $u \rightarrow v$ 的路径

代码咕了

$D$

$m$ 对是确定的，不能改变。剩下 $n(n - 1) / 2$ 条可以根据 $\forall i, j, k, C(i, j) \geq \min(C(i, k), C(k, j))$ 这条规则来推出

只要有树结构，就可以令其余对的权值等于路径上最小值。求出 $m$ 条边构成的最大生成森林。点对不连通则权值视作 $1$。

代码咕了

$E$

毒瘤大工业题，询问有多少区间，满足只保留区间内的点，构成的是一条链

考虑链是啥，就是边数 $= R - L$ 且每个点度数不超过 $2$ 且无环。

枚举 $R$。

无环、度数不超过 $2$：LCT + 双指针
边数 $= R - L$：线段树

代码咕了

$F$

就是使得每个区间至多被覆盖两次。显然是个费用流。

primal-dual 算法：初始运行一遍 spfa 求出 s 到每个点最短路，定义势函数 $h_x = dist(s, x)$，对于一条边 $(x, y)$ 将其边权修改为 $cost(x, y) + h_x - h_y$，就非负了，可以跑 dij 费用流，$O(mlogm * f)$

此处 $f = 2$

$Code$

$G$

考虑检验方程：$dp[i, j] = max( dp[i - 1, j], dp[i, j - 1], dp[i - 1, j - 1] + [a_i == b_j] )$

本质不同的串的 dp 过程也不一样。所以我们要去 dp 有多少种本质不同的 dp 过程：

注意到 $dp[i - K, i - K] = i - K$，只需要记录「当前位置的前 $K$ 个和后 $K$ 个 dp 值的差分状态」就能推出这 $2K$ 个的 dp 值，$f[i, s]$ 表示 $dp[ , ] = i$, 当前位置的前 $K$ 个和后 $K$ 个 dp 值的差分状态为 $S$。

$O(n 2^6 4 26 * 8)$ 但是跑过去了（

不难写，本质就是个压缩 + 解压缩。

$Code$